package arithmetic.demo18;

import java.util.*;


/**
 * 题目: 动态规划_下降路径的最小和
 */


class Solution {
    public int minFallingPathSum(int[][] nums) {
        
        int raw = nums.length, col = nums[0].length; 
        if(raw == 1 && col == 1) return nums[0][0];
        int[][] dp = new int[raw+2][col+2];

//        把所有数据都充满 最大值
        for(int i = 0; i <= raw + 1;i++) {
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }

        // 进行初始化第一行
        for(int j  = 1; j <= col ; j++) {
            dp[1][j] = nums[0][j-1];
        }

        // 从第二行进行状态转移
        for(int i = 2; i <= raw; i++) {
            for(int j = 1; j <= col ; j++) {
                int tmp = Math.min(dp[i-1][j-1], dp[i-1][j]);
                int min = Math.min(tmp, dp[i-1][j+1]);
                dp[i][j] = min + nums[i-1][j-1];
            }
        }

        int ret  = Integer.MAX_VALUE;
        // 得到最终结果
        for(int j = 1; j <= col ; j++) {
            ret = Math.min(dp[raw][j], ret);
        }


        return ret;

    }
}


class Test {
    public static void main(String[] args) {
        int[][] nums = new int[][]{{100,100,100,100,100},{100,100,100,100,100},{100,100,100,100,100},{100,100,100,100,100},{100,100,100,100,100}};
        Solution solution = new Solution();
        System.out.println(solution.minFallingPathSum(nums));
    }
}


/**
 * 题目： 贪心_最大数
 */


class Solution1 {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] str = new String[n];

        // 转化为字符串
        for(int i = 0; i< n; i++) {
            int num = nums[i];
            StringBuilder tmp = new StringBuilder();

          if(num == 0) {
            str[i] = "0";
            continue;
          }

        while(num != 0) {
            tmp.append((char)(num % 10 + '0'));
            num /= 10;
        }







            // 逆置
            tmp.reverse();

            str[i]= tmp.toString();
        }

        // 排序
        Arrays.sort(str,(a,b)->{
            String s1 = a+b;
            String s2 = b + a;
            return s2.compareTo(s1);
        });

        // 开始存储结果
        StringBuilder ret = new StringBuilder();



        for(int i =0; i< n ; i++) {
            ret.append(str[i]);
        }


        return  ret.toString();

    }
}


class Test1 {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9,0};
        Solution1 s = new Solution1();
        System.out.println(s.largestNumber(nums));
    }
}


/**
 * 题目： 贪心_摆动序列
 */

class Solution2 {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        // 特殊情况的一个点
        if(n == 1 )  return  1;

        int left= 0, right = 0, ret = 1;
        for(int i =0; i < n - 1; i++) {
            right = nums[i] - nums[i+1];

            // 如果右边出现相等的就跳到下一个
            if(right == 0) continue;


            // 如果顺序相反
            if(left * right <= 0) ret++;

            // 把后面的增减性放在前面
            left = right;

        }

        return ret;

    }
}


/**
 * 题目： 动态规划： 最小路径和
 */

class Solution3 {
    public int minPathSum(int[][] grid) {
        // 准备工作
        int raw = grid.length , col = grid[0].length;
        int[][] dp = new int[raw+1][col + 1];

        // 初始化
        for(int i = 0; i <= raw ; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[1][0] = dp[0][1] = 0;

        // 进行状态转移
        for(int i = 1; i <= raw ; i++){
            for(int j = 1; j <= col ; j++) {
                dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];
            }
        }


        return dp[raw][col];
    }
}